import javax.management.ListenerNotFoundException;
import java.util.*;

public class MyTree {
    static class TreeNode{//节点类
        TreeNode left;//左节点
        TreeNode right;//右节点
        int val;//节点中存储的值 - 用整形举例
        public TreeNode(){//不带参数的构造方法

        }
        public TreeNode(int val){//带参数的构造方法
            this.val = val;
        }
    }
    public TreeNode root;//树的根节点
    //前序遍历
    public void prevOrder(TreeNode root){
        if(root == null)
            return;
        System.out.println(root.val);
        prevOrder(root.left);
        prevOrder(root.right);
    }
    //中序遍历
    public void inOrder(TreeNode root){
        if(root == null)
            return;
        inOrder(root.left);
        System.out.println(root.val);
        inOrder(root.right);
    }
    //后续遍历
    public void postOrder(TreeNode root){
        if(root == null)
            return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val);
    }

    // 获取树中节点的个数
    int size(TreeNode root){
        if(root == null)
            return 0;
        return size(root.left) + size(root.right) + 1;
    }
    int count = 0;
    int size2(TreeNode root){
        if(root == null){
            return 0;
        }
        count++;
        size2(root.left);
        size2(root.right);
        return count;
    }
    // 获取叶子节点的个数
    int getLevelNodeCount(TreeNode root){
        if(root == null) return 0;
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLevelNodeCount(root.left)+getLevelNodeCount(root.right);
    }

    // 子问题思路-求叶子结点个数
    int nodeSize = 0;
    int getLevelNodeCount1(TreeNode root){
        if(root == null) return 0;
        if(root.left == null && root.right == null){
            nodeSize++;
        }
        getLevelNodeCount1(root.left);
        getLevelNodeCount1(root.right);
        return nodeSize;
    }
    // 获取第K层节点的个数=
    // root.left的k-1层 + root.right的k-1层
    int getKLevelNodeCount(TreeNode root,int k){
        if(root == null) return 0;
        if(k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right, k-1);
    }
    // 获取二叉树的高度
    int getHeight(TreeNode root){
        if(root == null) return 0;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return left > right ? left + 1 : right + 1;
    }
    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, int val){
        if(root == null) return null;
        if(root.val == val) return root;
        TreeNode left = find(root.left,val);
        TreeNode right = find(root.right,val);
        if(left != null){
            return left;
        }
        if(right != null){
            return right;
        }
        return null;
    }
    //层序遍历
    void levelOrder(TreeNode root){
        if(root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size != 0){
                TreeNode node = queue.poll();
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
                size--;
                System.out.print(node.val+" ");
            }
        }
    }
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root){
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node != null){
                queue.offer(node.left);
                queue.offer(node.right);
            }else {
                break;
            }
        }
        while(!queue.isEmpty()){
            if(queue.poll()!=null)
                return false;
        }
        return true;
    }
}
class Solution {
    public int deleteGreatestValue(int[][] grid) {
        for(int i=0; i<grid.length; i++){
            Arrays.sort(grid[i]);
        }
        int sum = 0;
        for(int j=0; j<grid[0].length; j++){
            int tmp = grid[0][j];
            for(int i=1; i<grid.length; i++){
                tmp = Math.max(grid[i][j],tmp);
            }
            sum += tmp;
        }
        return sum;
    }
}